package web

import "strings"

// node 表示Trie树中的一个节点
// pattern: 待匹配路由，例如 /p/:lang
// part: 路由中的一部分，例如 :lang
// children: 子节点数组
// isWild: 是否为模糊匹配，当part含有 : 或 * 时为true
type node struct {
	pattern  string  // 待匹配路由，例如 /p/:lang
	part     string  // 路由中的一部分，例如 :lang
	children []*node // 子节点，例如 [doc, tutorial, intro]
	isWild   bool    // 是否精确匹配，part 含有 : 或 * 时为true
}

// matchChild 查找第一个匹配的子节点
// part: 要匹配的路径部分
// 返回: 找到的子节点，如果没有找到则返回nil
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

// matchChildren 查找所有匹配的子节点
// part: 要匹配的路径部分
// 返回: 所有匹配的子节点组成的数组
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

// insert 向Trie树中插入路由模式
// pattern: 完整的路由模式，例如 "/p/:lang"
// parts: 路由模式拆分后的部分数组
// height: 当前插入的深度
func (n *node) insert(pattern string, parts []string, height int) {
	if len(parts) == height {
		n.pattern = pattern
		return
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}
	child.insert(pattern, parts, height+1)
}

// search 在Trie树中查找匹配的路由模式
// parts: 请求路径拆分后的部分数组
// height: 当前查找的深度
// 返回: 找到的匹配节点，如果没有找到则返回nil
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}

	return nil
}
